package org.test.analysis.sort;

import junit.framework.Assert;

import org.junit.Test;

public class QuickSort {
	/**
	 * 
	 * @param s
	 *            数组
	 * @param k
	 *            s中index为k的数做为轴,一般为0就行了。
	 * @return 返回轴的index
	 */
	public int partition(char s[], int k) {
		char p = s[k];// 轴
		char tmp;// 临时变量
		int i = 0, j = s.length - 1;
		for (; i <= j; j--, i++) {
			for (; (s[i] <= p)&&(j>i); i++) {// i自加,直到指向比p大的元素,若 i,j 相等，则不用再过了。
			}
			for (; (s[j] > p)&&(j>0); j--) {// j自减，直到指向比p小的元素后交换i,若i,j相等时，则不用减了
			}
			// 交换
			if(i>=j){ //i,j相等了，直接不用i++,j--了
				break;
			}
			tmp = s[j];
			s[j] = s[i];
			s[i] = tmp;
		}

		// 把轴放到中间
		tmp = s[j];
		s[j] = s[k];
		s[k] = tmp;

		return j;
	}

	@Test
	public void testpartition() {
		char[] r = { 'f', 'c', 'z', 'e', 'w' };
		partition(r, 0);
		Assert.assertEquals((new String(r)).toString(), "ecfzw");
		
		char[] r1 = { 'f', 'c'};
		partition(r1, 0);
		Assert.assertEquals((new String(r1)).toString(), "cf");
		
		char[] r3 = { 'c', 'f','w'};
		partition(r3, 0);
		Assert.assertEquals((new String(r3)).toString(), "cfw");
		
		char[] r4 = { 'f'};
		partition(r4, 0);
		Assert.assertEquals((new String(r4)).toString(), "f");

		char[] r2 = { 'e', 'c', 'a', 'i', 'h', 'b', 'd', 'g' };
		partition(r2, 0);
		Assert.assertEquals((new String(r2)).toString(), "bcadehig");
		
	}

	/**
	 * 把s用快速排序排
	 * 
	 * @param s
	 */
	public void quicksort(char s[]) {
		if(s.length>1){
			int k = partition(s, 0);// k为轴index
			char[] r1 = new char[k];
			char[] r2 = new char[s.length-k-1];
			
			Sutil.copycharArray(0,k-1,s,r1);//填充到r1
			Sutil.copycharArray(k+1, s.length-1, s, r2);
			
			quicksort(r1);
			quicksort(r2);
			
			//下面用来把r1，s[k],和r2合起来放到s中
			char[] r3 = new char[r1.length+1];
			Sutil.copycharArray(0, r1.length-1, r1, r3);
			r3[r3.length-1]=s[k];
			Sutil.concat(r3, r2, s);
		}
	}
	
	@Test
	public void testquicksort(){
		char[] s = {'z','a','k','j','k','j','f'};
		quicksort(s);
		System.out.println(s);
		
		char[] s1 = {'z','k','j','k','j','f'};
		quicksort(s1);
		System.out.println(s1);
		
		char[] s2 = {'z','k','j','k','f','a','b'};
		quicksort(s2);
		System.out.println(s2);
	}
	
	
	


}
